Finite State Machines (FSMs) have frequently been used as a technique for specifying dialog flows. FSMs consist of a set of system states along with a set of labeled transitions (arcs between states) which define how to move from one state to another. In recent years, it has become increasingly popular in certain areas to use extensions to FSMs known as Harel Statecharts (Statecharts), or Hierarchical State Machines (HSMs). This is primarily due to their inclusion in the UML 2.0 standard, although they have also found uses in other areas, such as the design of human-computer interaction control logic. Statecharts are similar in many respects to FSMs, but they are augmented with a variety of additional constructs, including hierarchical states, guard conditions, actions on transitions, parallel states and broadcast communication. These generalizations, while not mathematically increasing the expressive power of Statecharts with respect to FSMs, can greatly reduce the representational complexity of a given state machine specification when compared with a behaviorally equivalent FSM. Statecharts are therefore better suited than FSMs for modeling complex reactive systems, of which user interfaces are prime examples. Despite these advantages over FSMs, it remains the case that designing a Statechart for specifying a dialog flow can be a very complex task, especially at the very initial stages of dialog design. The dialog designer must still determine the relevant set of states and transitions, which actions must be executed, and in what order. Anything that can help automate this process, especially at the initial stages, would make this process less difficult and error prone.
Statecharts are known in the art, and have been used with dialog systems and as starting points for software generation. However, these statecharts have not been developed automatically from higher-level descriptions or using goal specifications. A Statechart may be represented in graphical form, in a statechart diagram, or by a textual language, such as the State Chart eXtensible Markup Language (SCXML), that specifies user interaction control logic. It may also be represented directly in code. Our invention covers all of these possibilities.
Feature models have been used to generate deterministic Statecharts. However, features models are quite different from goals specified over a data model, and are more like domain models rather than compact descriptions of desired states of affairs.
Declarative constructs (other than goals) have been used to generate simple state machines, but not for the generation of Statecharts.